package cn.edu.njust.alg.leetcode;

/**
 * 创建时间：2015年6月15日 上午11:47:37 项目名称：AlgorithmExercise
 * 
 * @author Zhou Xiumin
 * @version 1.0
 * @since JDK 1.7.0_21 文件名称：Leetcode_0_t.java 类说明：
 */
public class Leetcode_29_Divide_Two_Integers {

	public static int divide(int dividend, int divisor) {
		if (divisor == 0) {
			return Integer.MAX_VALUE;
		} else if (divisor == 1) {
			return dividend;
		} else if (divisor == -1) {
			if (dividend == Integer.MIN_VALUE) {
				return Integer.MAX_VALUE;
			}
			return -dividend;
		} else if (divisor == Integer.MIN_VALUE) {
			if (dividend == Integer.MIN_VALUE) {
				return 1;
			} else {
				return 0;
			}
		} else if (dividend == Integer.MIN_VALUE) {
			if (divisor < 0) {
				return divide(dividend - divisor, divisor) + 1;
			} else {
				return divide(dividend + divisor, divisor) - 1;
			}

		} else if (Math.abs(dividend) < Math.abs(divisor) || dividend == 0) {
			return 0;
		} else if (dividend == divisor) {
			return 1;
		} else if (dividend < 0) {
			return -divide(-dividend, divisor);
		} else if (divisor < 0) {
			return -divide(dividend, -divisor);
		}
		int k = 1;
		int t = dividend;
		int d = divisor;
		while (t >> 1 > divisor) {
			k = k << 1;
			d = d << 1;
			t = t >> 1;
		}
		return k + divide(dividend - d, divisor);
	}

	public static void main(String[] args) {
		System.out.println(divide(-2147483648, 2));
	}

}
